#!/usr/bin/env python3

"""
博客版本
循环单链表
"""


class Node:
    """
    定义node结点
    """
    count = 0

    def __init__(self, elem):
        self.elem = elem
        self.next = None
        Node.count += 1

    def __del__(self):
        Node.count -= 1


class CSList:
    """
    循环单链表
    """

    def __init__(self):
        self.__head = Node

    def is_empty(self):
        return self.__head is Node

    @staticmethod
    def get_length():
        print("创建的数据结点数目: ", Node.count)
        return Node.count

    def create(self):
        elem = input("请输入结点值: ")
        cur = self.__head

        while elem != '#':
            self.add_rear(elem)
            elem = input("请输入结点值: ")

    def add_head(self, elem):
        node = Node(elem)

        if self.is_empty():
            self.__head = node
            node.next = self.__head
        else:
            cur = self.__head
            #  遍历结点, 找到链表的结尾
            while cur.next != self.__head:
                cur = cur.next
            #  插入node结点
            node.next = self.__head
            cur.next = node
            #  重新找到头结点
            self.__head = node

    def add_rear(self, elem):
        node = Node(elem)

        if self.is_empty():
            self.__head = node
            node.next = self.__head
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            cur.next = node
            node.next = self.__head

    def insert_data(self):
        pos = int(input("请输入插入位置: "))
        elem = input("请输入结点值: ")

        index = self.get_length()
        if (pos < 1) or (int(pos) > index):
            print("insert pos error")
            return

        if pos == 1:
            self.add_head(elem)
        elif pos == self.get_length():
            self.add_rear(elem)
        else:
            cur = self.__head
            node = Node(elem)
            #  找出指定位置结点
            while pos:
                pos -= 1
                cur = cur.next
            #  插入结点
            node.next = cur.next
            cur.next = node

    def del_data(self):
        elem = input("请输入待删除数据: ")
        if self.is_empty():
            print("请先添加数据")
            return
        cur = self.__head
        if cur.elem == elem:
            if cur.next != self.__head:
                while cur.next != self.__head:
                    cur = cur.next
                self.__head = self.__head.next
                cur.next = self.__head
            else:
                self.__head = None
        else:
            pre = self.__head
            while cur.next != self.__head:
                if cur.elem == elem:
                    pre.next = cur.next
                    pre = cur
                    cur = cur.next
                else:
                    pre = cur
                    cur = cur.next
            if cur.elem == elem:
                pre.next = self.__head
            else:
                print("所查找的数据未存入")
                return

    def travel(self):
        if self.is_empty():
            print("空链表")
            return 0

        #  设置遍历指针
        cur = self.__head
        while cur.next != self.__head:
            print("Cur node data is :", cur.elem)
            cur = cur.next
        print("Cur node data is :", cur.elem)


if __name__== "__main__":
    csl_class = CSList()
    csl_class.create()
    csl_class.insert_data()
    csl_class.travel()
    csl_class.del_data()
    csl_class.travel()


